#include <bits/stdc++.h>
using namespace std;

/*
1963. 使字符串平衡的最小交换次数
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

字符串是一个空字符串，或者
字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

 

示例 1：

输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。
示例 2：

输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。
示例 3：

输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。
 

提示：

n == s.length
2 <= n <= 106
n 为偶数
s[i] 为'[' 或 ']'
开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2
*/

// 法一
class Solution {
	public:
	int minSwaps(string s) {
		int balance = 0; // 记录括号的平衡状态
		int swaps = 0;   // 记录需要的交换次数

		// 遍历字符串
		for (char ch : s) {
			if (ch == '[')
				balance++; // 增加平衡状态
			else
				balance--; // 遇到 ']' 减少平衡状态

			// 如果 balance 变负，表示有更多的 ']' 需要配对，进行交换
			if (balance < 0) {
				swaps++;
				balance = 1; // 重置 恢复
			}
		}
		return swaps;
	}
};

// 法二
class Solution {
	public:
	int minSwaps(string s) {
		int leftBracket = 0;  // 用于记录当前未匹配的 '[' 的数量
		int ans = 0;          // 用于记录最小的交换次数
		// 遍历字符串中的每个字符
		for (const auto ch : s) {
			if (ch == '[') {
				leftBracket += 1;  // 遇到 '['，增加未匹配的 '[' 数量
			} else {
				// 遇到 ']'，如果有未匹配的 '['，则配对
				if (leftBracket > 0) {
					leftBracket -= 1;  // 配对一个 '['，减少未匹配的 '[' 数量
				} else {
					// 如果没有未匹配的 '['，则需要交换，将这个 ']' 和某个 '[' 配对
					ans += 1;          // 需要一次交换
					leftBracket += 1;  // 假设我们交换了一个 '['，使得 '[' 的数量增加
				}
			}
		}
		return ans;  // 返回需要的最小交换次数
	}
};
